/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.easy._563;

/**
 *
 * 给定一个二叉树，计算整个树的坡度。
 *
 * 一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
 *
 * 整个树的坡度就是其所有节点的坡度之和。
 *
 * 示例:
 *
 * 输入:
 *          1
 *        /   \
 *       2     3
 * 输出: 1
 * 解释:
 * 结点的坡度 2 : 0
 * 结点的坡度 3 : 0
 * 结点的坡度 1 : |2-3| = 1
 * 树的坡度 : 0 + 0 + 1 = 1
 * 注意:
 *
 * 任何子树的结点的和不会超过32位整数的范围。
 * 坡度的值不会超过32位整数的范围。
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.easy._563
 * @ClassName: BinaryTree
 * @Author: linyaonan
 * @Date: 2020/1/3 9:12
 */
public class BinaryTree {
    int sum = 0;
    public int findTilt(TreeNode root) {
        getTreeNode(root, 0);
        return sum;
    }

    private int getTreeNode(TreeNode node, int count) {
        if (node == null) {
            return count;
        } else {
            int left = getTreeNode(node.left, count);
            int right = getTreeNode(node.right, count);
            count += (node.val + left + right);
            sum += Math.abs(left - right);
            return count;
        }
    }


}
